The present invention relates to a method and apparatus for modular inversion which is carried out for information security, for example, in digital cryptosystems and digital authentication systems which use encryption key generation, digital signature and blind signature schemes, and elliptic cryptosystem and so forth. The invention also pertains to a recording medium with the modular inversion method recorded thereon.
In the field of information security it is well-known that the calculation of modular inverse over a prime finite field GF(p) (where p is a prime) or residue class ring Z/NZ (Z is a group of integers and N is a positive integer) takes a wide variety of forms, some of which will be described below.
(a) Generation of sum (x3, y3) of two points (x1, y1) and (x2, y3) on an elliptic curve E/GF(p):
xcex=(y2xe2x88x92y1)/(x2xe2x88x92x1)mod pxe2x80x83xe2x80x83(a-1)
x3=xcex2xe2x88x92x1xe2x88x92x2 mod pxe2x80x83xe2x80x83(a-2)
y3=xcex(x1xe2x88x92x3)xe2x88x92y1 mod pxe2x80x83xe2x80x83(a-3)
(b) Part of signature generation of digital signature system ESIGN:
y=w/(kxkxe2x88x921)mod pxe2x80x83xe2x80x83(b-1)
where x is an integer 1xe2x89xa6xxe2x89xa6pqxe2x88x921, w is an integer in the range of 0xe2x89xa6wxe2x89xa6pxe2x88x921, kxcex5Z, and p and q are primes.
(c) Blind signature generation of digital signature system RSA:
sxe2x80x2=(rem)d mod Nxe2x80x83xe2x80x83(c-1)
s=sxe2x80x2/r mod Nxe2x80x83xe2x80x83(c-2)
xe2x80x83where r and m are integers 0xe2x89xa6r and mxe2x89xa6Nxe2x88x921, and e and d are integers 1xe2x89xa6e and dxe2x89xa6xcfx86(N)xe2x88x921, respectively.
The above examples use modular multiplications and modular inversions. The Montgomery method has been proposed to efficiently calculate modular residues. Listed below are definitions of some types of modular inversion that suit the Montgomery method.
where B=2n, n is the number of bits of N, N less than B less than 2N and Xxcex5Z/NZ The modular inversion mentioned herein includes any types of modular inversion as well as the above. Replacing the N with a prime p, the abovementioned inverse will be an inverse over GF(p). The following description will be given only of Z/NZ
Conventionally, for inputs X and N where X is equal to or greater than zero and smaller than N, a modular inverse of X over Z/NZ is calculated, for example, using an extended binary GCD method (extended binary Greatest Common Divisor method, an algorithm for producing Xxe2x88x9212k mod N and k, the former being expressed by bgcd(X, N)) The following example will be described in connection with the calculation of a Montgomery inverse.
Method 1:
Step 1: Calculate S and k by
S=bgcd(X, N)=Xxe2x88x9212k mod Nxe2x80x83xe2x80x83(1)
where nxe2x89xa6kxe2x89xa62n.
Step 2: Calculate a modular inverse R by
R=S22nxe2x88x92k mod N=Nxe2x88x92122n mod Nxe2x80x83xe2x80x83(2)
Step 1 is a process of executing the extended binary GCD algorithm for the inputs X and N. Since 2nxe2x88x92k greater than 0, Step 2 is to calculate multiplication by power of 2.
The calculation (b) can also be used to obtain a Montgomery inverse by the method 2 shown below.
Incidentally, when d less than 0,
(a) Multiplication by power of 2: X2dmod N
(b) Division by power of 2: X2xe2x88x92dmod N
the calculation (b) can be done faster than (a).
Method 2:
Step 1: Y=X2xe2x88x92n mod Nxe2x80x83xe2x80x83(3)
Step 2: S=bgcd(Y, N)(=Xxe2x88x9212n+k mod N)xe2x80x83xe2x80x83(4)
Step 3: R=S2xe2x88x92(kxe2x88x92n) mod N(=Xxe2x88x92122n mod N)xe2x80x83xe2x80x83(5)
Since kxe2x88x92nxe2x89xa70, Step 3 performs a division by power of 2.
If the multiplication (a) and the division (b) consumes the same amount of time, then Method 1 involving the smaller number of steps enables the calculation to be made in a shorter time than in the case of using Method 2. In practice, however, since the division (b) can be conducted in a shorter time, it is presumed that the modular inversion by Method 2 may sometimes be processed in a shorter time.
Assuming that N is too large a value to calculate or process by an ordinary computer or processor at a time, the amounts of time for the calculations (a) and (b) increase as d becomes larger.
For example, in the case of using a method in which elementary operations are
(a)xe2x80x2 Multiplication by 2: X2 mod N
(b)xe2x80x2 Division by 2: X2xe2x88x921 mod N
and the calculation (a)xe2x80x2 is carried out d times as the calculation (a), the time for calculation (a) is d times longer than the time for calculation (a)xe2x80x2. Similarly, the time for calculation (b) is d times longer than that for calculation (b)xe2x80x2. The operations corresponding to calculations (a)xe2x80x2 and (b)xe2x80x2 will hereinafter be referred to as an elementary operation.
Method 2 conducts division by power of 2 instead of performing multiplication by power of 2 in Method 1, but needs to perform the elementary operation a larger number of times than does Method 1.
For example, when k=1.41n (It has been experimentally demonstrated that k and n bear this relation on average.) Method 1 performs the Bgcd algorithm, and besides, the elementary operation 0.59 times in Step 2. On the other hand, Method 2 performs the elementary operation n times in Step 1 and 0.41 n times in Step 3 in addition to the Bgcd algorithm, and hence it conducts the elementary calculation a total of 1.41n times. Accordingly, there is no possibility of Method 2 becoming faster than Method 1 unless the division by power of 2 is considerably faster than the multiplication by power of 2 (more than 2.3 times faster in the above example). Conversely, even if means for speeding up the multiplication by power 2, though not feasible at present, is available, no speedups are possible if only the division by power of 2 occurs.
It is an object of the present invention to provide a calculating method which permits reduction of the time for modular inversion necessary for information security, a modular inversion apparatus using the method, and a recording medium with a program recorded thereon for implementing the method.
Another object of the present invention is to provide a modular inversion method which enables multiplication and division by power of 2 to be performed efficiently and hence in a short time, a modular inversion apparatus using the method, and a recording medium with a program recorded thereon for implementing the method.
Still another object of the present invention is to provide a modular inversion method which enables an extended binary GCD to be calculated efficiently and hence in a short time, a modular inversion apparatus using the method, and a recording medium with a program recorded thereon for implementing the method.
The modular inversion method, the apparatus using the method and the program recorded on a recording medium for implementing the method according to a first aspect of the present invention:
(a) calculate Y, for n-bit input values X and N, by the following equation using a predetermined value t
Y=X2xe2x88x92t mod N;
(b) calculate an extended binary GCD for said Y and N by the following equation to obtain S and k
S=bgcd(Y, N)=Yxe2x88x9212k mod N;
and
(c) perform the following equation using said S, k and t
R=S2xe2x88x92(k+txe2x88x92m) mod N, m=0, n, or 2n
and output said R as the modular inversion result.
According to a second aspect of the present invention, in the above modular inversion a division of input values S and N by power of 2 represented as S2xe2x88x92w mod N, w being a predetermined number of bits to be calculated or processed at a time, comprises the steps of:
(a) calculating nxe2x80x2=xe2x88x92Nxe2x88x921 mod 2w for input values S and N;
(b) calculating sxe2x80x2=Snxe2x80x2 mod 2w from said nxe2x80x2 and S;
(c) calculating q=S+sxe2x80x2N from said sxe2x80x2, S and N; and
(d) calculating q2w from said q and w as the result of said division by power of 2.
According to a third aspect of the present invention, in the above modular inversion, letting the number of bits that an apparatus for modular inversion processes at a time be represented by M, a multiplication of input values S and N by power of 2 represented as S2w mod N, w being a predetermined number of bits to be calculated or processed at a time, comprises the steps of:
(a) calculating nxe2x80x2=2n+Mxe2x88x921/N for said input values S and N;
(b) calculating txe2x80x2=snxe2x80x2/22Mxe2x88x92wxe2x88x921 from said nxe2x80x2 and the value s of upper M bits of said S;
(c) calculating Sxe2x80x2=S2wxe2x88x92txe2x80x2N from said S, N, txe2x80x2 and w; and
(d) comparing said Sxe2x80x2 and N, and if Sxe2x80x2 greater than N, repeating an update Sxe2x80x2←Sxe2x80x2xe2x88x92N to obtain Sxe2x80x2 satisfying Sxe2x80x2xe2x89xa6N, and if Sxe2x80x2xe2x89xa6N. obtaining said value Sxe2x80x2 as the result of said multiplication by power of 2.
According to a fourth aspect of the present invention, said extended binary GCD algorithm in said modular inversion comprising:
(b-1) a step of setting U0=Y and V0=N for said Y and N, initializing S0=0, T0=1 and k=0, and storing said U0, V0, S0, T0 and k in storage means;
(b-2) a GCD simulation step of calculating, from said values U0 and V0 stored in said storage means, uu, uv, vv and vu which satisfies, for predetermined wxe2x80x2,
gcd(U0, V0)=gcd(|uuU0xe2x88x92uvV0|/2wxe2x80x2, |vvV0xe2x88x92vuU0|/2wxe2x80x2),
adding said wxe2x80x2 to said k in said storage means to obtain an updated value k, and storing said updated value k in said storage means together with said values uu, uv, vv and vu;
(b-3) a multi-precision calculation step of calculating
V1=(vvV0xe2x88x92uuU0)/2wxe2x80x2,
U1=(uuU0xe2x88x92uvV0)/2wxe2x80x2,
S1=uuS0+uuY0,
T1=vuS0+vvT0,
for said values U0, V0, T0, uu, vv and vu stored in said storage means, temporarily storing V1, N1, S1 and T1 in said storage means, determining whether said value V1 is negative or not, and if negative, inverting the signs of said temporarily stored values V1 and T1, determining whether said value U1 is negative or not, if negative, inverting the signs of said temporarily stored values U1 and S1, and updating said values U0, V0, T0 and So in said storage means with said temporarily stored values U1, V1, S1 and T1, said wxe2x80x2 being an integer equal to or greater than 4;
(b-4) a final processing step of calculating uu, uv, vu, vv and c which satisfy
|uuU0xe2x88x92uvV0|/2c=gcd(U0, V0)
|vvV0xe2x88x92vuU0|/2c=0
for said values U0, V0, t0 and S0 stored in said storage means, calculating Sxe2x80x2=uuS0+uvT0, and adding said value c to said value k to update it; and
(b-5) an output step of outputting said value Sxe2x80x2 and k as the results S and k of said extended binary GCD calculation.